package com.szrt.day20170410;



import java.util.Arrays;
import org.junit.Test;
import com.szrt.utils.ArrayUtil;


/**
 * 使用快速排序
 * @author scott-13926583118
 * 2017年4月10日
 *
 */
public class QuickSortTest {
	
	
	
	@Test
	public void sortTest2() throws Exception {
		int[] array ={49,38,65,97,76,13,27,11};
		
		Arrays.sort(array);
		
		ArrayUtil.printArry(array);
	}
	
	@Test
	public void sortTest() throws Exception {
		
		int[] array ={49,38,65,97,76,13,27,11,11};
		sort(array, 0, array.length-1);
		
		//根据快速排序的思想写1个方法
		System.out.println("最终结果============");
		ArrayUtil.printArry(array);
	}
	
	
	
	/**
	 * 快速排序的核心方法
	 * @param array   要排序的数组
	 * @param begin   下标从哪里开始  有包括自己本身
	 * @param end     下标从哪里开始  有包括自己本身
	 */
	public void sort(int[] array,int begin,int end){
		//具体的逻辑
		int i=begin;
		int j=end;
		ArrayUtil.printArry(array);
		System.out.println("begin="+begin + ",end="+end);
		if(begin>=end){
			//结束整个方法
			System.out.println("结束方法。不用排序...");
			return;
		}
		//key 关键元素
		int key = array[i];
		
		
		while(true){
			//从右往左扫描
			while(j>i){
				//如果右边的数比key要小 把i和j交换位置  就不找了
				if(array[j]<key){
					ArrayUtil.changePosition(array, i, j);
					break;
				}else{
					j--;
				}
			}
			
			
			//从左往右扫描
			while(j>i){
				//如果右边的数比key要小 把i和j交换位置  就不找了
				if(array[i]>key){
					ArrayUtil.changePosition(array, i, j);
					break;
				}else{
					i++;
				}
			}
			
			//结束1趟循环
			if(j==i){
				break;
			}
		}
		
		//后面的循环跟前面的循环一样  递归
		//左边的子数组
		sort(array, begin, i-1);
		
		//右边的子数组
		sort(array, i+1, end);
		
	}

}
